package _01_排序;

import _01_排序.tools.Integers;

/*
    ◼ 执行流程
    ① 从序列中找出最大的那个元素，然后与最末尾的元素交换位置
    ✓ 执行完一轮后，最末尾的那个元素就是最大的元素
    ② 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①


    ◼ 选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
    ◼ 最好、最坏、平均时间复杂度：O(n^2)，空间复杂度：O(1)，属于不稳定排序

    选择排序只跟最大的交换
 */
public class SelectionSort02<E extends Comparable<E>> extends Sort<E> {
    public static void main(String[] args) {
        Integer[] array = Integers.random(10,1,100);
        selectionSort(array);
        Integers.println(array);
    }

    public static void selectionSort(Integer[] array){
        for(int end = array.length-1;end>0;end--){
            int maxIndex = 0;
            for(int begin = 1;begin<=end;++begin){
                if(array[maxIndex]<=array[begin]){
                    maxIndex = begin;
                }
            }
            int tmp = array[maxIndex];
            array[maxIndex] = array[end];
            array[end] = tmp;
        }
    }

    //重写排序方法
    @Override
    protected void sort() {
        for(int end = array.length-1;end>0;end--){
            int maxIndex =0; //假设最大位置的索引是0
            for(int begin=1;begin<=end;begin++){
                if(cmp(maxIndex,begin)<0){
                    maxIndex = begin;
                }
            }
            //一趟比较完以后，将最大值放到最后
            /*int tmp = array[maxIndex];
            array[maxIndex] = array[end];
            array[end] = tmp;*/
            swap(maxIndex,end);
        }
    }
}
